递归与动态规划——跳跃游戏

Posted on | In ,

题目：给定数组arr,其中arr[i]==k表示从位置i最多能向右跳k个距离。如果从位置0出发，最少跳几次能跳到arr最后的位置上。
例：
arr=[3,2,3,1,1,4]
arr[0]=3，跳两次到位置2，arr[2]=3跳3次到达最后位置。因此最少跳两次。
要求：若arr长度为N，要求时间复杂度为O(N)，额外空间复杂度为O(1)。

实现：

  1. 定义3个int型变量jump、cur、next，其中
    jump表示目前跳了多少步；
    cur表示跳了jump步后，最远能达到的位置；
    next表示如果再多跳一步，最远能达到的位置。
  2. 遍历数组
    1）如果cur>=i，说明跳jump步可以到达i，此时什么也不用做。
    2）如果cur<i，说明跳jump步不能到达i，此时需要jump++，cur=next。表示多跳了一步，cur更新成跳jump+1位置最远能达到的位置，即next的值。
  3. 将next更新为多跳一步，最远能达到的位置，即next=max{next,i+arr[i]}。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int jump(int[] arr){
	if (arr == null || arr.length == 0){
		return 0;
	}
	int jump = 0;
	int cur = 0;
	int next = 0;
	for (int i = 0; i < arr.length; i++){
		if (cur < i) {
			jump++;
			cur = next;
		}
		next = Math.max(next, i + arr[i]);
	}
	return jump;
}